package algorithm.swordoff;

/**
 * 青蛙跳台阶问题
 * 与主站70题相同
 *
 * dp[k] = dp[k-1] + dp[k-2]
 *
 * 本身不难,注意题目要求的模运算
 * (a + b) % p = (a % p + b % p) % p
 * (a - b) % p = (a % p - b % p ) % p
 * (a * b) % p = (a % p * b % p) % p
 * (a^b) % p = ((a % p)^b) % p
 * 结合律：
 * ((a+b) % p + c) % p = (a + (b+c) % p) % p
 * ((a*b) % p * c) % p = (a * (b*c) % p) % p
 * 交换律：
 * (a + b) % p = (b+a) % p
 * (a * b) % p = (b * a) % p
 * 分配律：
 * ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
 *
 */

public class SQ10_2 {
    public int numWays(int n) {
        int dpLastTwo = 1;
        int dpLastOne = 1;

        for (int i = 2; i <= n; i++) {
            int temp = dpLastOne;
            // 注意 dp[k-2] 是由 dp[k-1] 而来,所以不会越界,只会 dp[k-1] 越界
            // 这里容易出错,括号外的模运算绝不能丢
            dpLastOne = (dpLastTwo%1000000007 + dpLastOne%1000000007)%1000000007;
            dpLastTwo = temp;
        }

        return dpLastOne;
    }
}
